import java.util.Arrays;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Description:
 *
 * @author: chengrongkai
 * Date: 2021/3/26
 */
public class Sort {

    public static void main(String[] args) {
        int[] nums = {2,3,5,1,18,6,7};
        doSort(nums,5);
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            System.out.println(num);
        }
    }

    public static void doSort(int[] nums,int type){
        switch (type){
            case 1: bubbleSort(nums);break;
            case 2: insertSort(nums);break;
            case 3: selectSort(nums);break;
            case 4: mergeSort(nums);break;
            case 5: quickSort(nums);break;
        }
    }

    /**
     * 冒泡排序
     * @param nums
     */
    public static void bubbleSort(int[] nums){
//        定义一个变量，如果当前这轮遍历没发生交换，则说明已经完全排好序了，直接return
        boolean hasChange = true;
        for (int i = 0; i < nums.length-1&&hasChange; i++) {
            hasChange = false;
            for (int j = 0; j < nums.length-i-1; j++) {
                if (nums[j + 1] < nums[j]){
                    int temp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = temp;
                    hasChange = true;
                }

            }
        }
    }

    /**
     * 插入排序
     * 每次遍历找到前面一个合适的位置插入，前面顺序不对的元素全部后移
     * @param nums
     */
    public static void insertSort(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int j = i-1;
            while (j>=0&&num<nums[j]) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] =  num;
        }
    }

    /**
     * 选择排序，每次选择一个最小的值加入到已排序的队列
     * @param nums
     */
    public static void selectSort(int[] nums){
        for (int i = 0; i < nums.length-1; i++) {
            int num = nums[i];
            int minIndex = i;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] < num){
                    minIndex = j;
                    num = nums[j];
                }
            }
            if (minIndex > i){
                int temp = nums[minIndex];
                nums[minIndex] = nums[i];
                nums[i] = temp;
            }

        }
    }

    /**
     * 归并排序
     * @param nums
     */
    public static void mergeSort(int[] nums){
        int[] result = new int[nums.length];
        mergeSort(nums,result,0,nums.length-1);
    }

    /**
     * 归并排序
     * @param nums 原始数组
     * @param result 结果数组
     * @param start 开始
     * @param end 结束
     */
    public static void mergeSort(int[] nums,int[] result,int start,int end){
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        mergeSort(nums, result, start1, end1);
        mergeSort(nums, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2)
            result[k++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];
        while (start1 <= end1)
            result[k++] = nums[start1++];
        while (start2 <= end2)
            result[k++] = nums[start2++];
        for (k = start; k <= end; k++)
            nums[k] = result[k];
    }

    /**
     * 快速排序也采用了分治的思想：把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组
     * @param nums
     */
    public static void quickSort(int[] nums){
        quickSort(nums,0,nums.length-1);
    }

    public static void quickSort(int[] nums,int low,int high){
        if (low >= high) {
            return;
        }
        int p = partition(nums, low, high);
        quickSort(nums, low, p - 1);
        quickSort(nums, p + 1, high);
    }

    public static int partition(int[] nums,int low,int high){
        int less = low - 1, more = high;
        while (low < more) {
            if (nums[low] < nums[high]) {
                swap(nums, ++less, low++);
            } else if (nums[low] > nums[high]) {
                swap(nums, --more, low);
            } else {
                ++low;
            }
        }
        swap(nums, more, high);
        return less+1;
//        return new int[] {less + 1, more};
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
